//带头节点的双向链表
#include<iostream>

using namespace std;

template<class T>
class List
{
private:
	class ListNode
	{
	public:
		T _value;
		ListNode* _next = nullptr;
		ListNode* _prev = nullptr;
		ListNode() {}
		ListNode(T vlaue)
			:_value(vlaue)
		{}
	};
public:
	List()
	{
		_head = new ListNode;
	}
	//打印
	void printList()
	{
		if (Length == 0)return;
		ListNode* cur = _head->_next;
		cout << "List";
		int n = Length;
		while (n--)
		{
			cout << "->" << cur->_value ;
			cur = cur->_next;
		}
		cout << endl;
	}
	//尾插
	void ListPushBack(T x)
	{
		ListNode* newnode = new ListNode(x);
		ListNode* cur = _head;
		int n = Length;
		while (n--)
		{
			cur = cur->_next;
		}
		cur->_next = newnode;
		newnode->_prev = cur;
		Length++;
	}
	//头插
	void ListPushFront(T x)
	{
		
		if (ListEmpty())
		{
			ListPushBack(x);
			return;
		}
		else
		{
			ListNode* newnode = new ListNode(x);
			ListNode* cur = _head->_next;
			_head->_next = newnode;
			cur->_prev = newnode;
			newnode->_prev = _head;
			newnode->_next = cur;
			
		}
		Length++;
	}
	//尾删
	void ListPopBack()
	{
		if (ListEmpty())return;
		ListNode* cur = _head;
		int n = Length;
		while (n--)
		{
			cur = cur->_next;
		}
		cur->_prev->_next = nullptr;
		delete cur;
		Length--;
	}
	//头删
	void ListPopFront()
	{
		if (ListEmpty())return;
		if (Length == 1)
		{
			ListNode* cur = _head->_next;
			_head->_next = nullptr;
			delete cur;
		}
		else
		{
			ListNode* cur = _head->_next;
			ListNode* next = cur->_next;
			next->_prev = _head;
			_head->_next = next;
			delete cur;
		}
		Length--;
	}
	//判断链表是否为空
	bool ListEmpty()
	{
		return Length==0;
	}
	void ListInsert(int pos, T x)
	{
		if (pos > Length || pos < 0)return;
		if (pos == 0)
		{
			ListPushFront(x);
			return;
		}
		else if (pos == Length)
		{
			return;
		}
		else 
		{
			ListNode* newnode = new ListNode(x);
			ListNode* cur = _head;
			int n = pos+1;
			while (n--)
			{
				cur = cur->_next;
			}
			ListNode* prev = cur->_prev;
			cur->_prev = newnode;
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			
		}
		Length++;
	}
	//删除pos位置节点
	void ListErase(int pos)
	{
		if (pos >= Length)return;
		if (pos == Length - 1)
		{
			ListPopBack();
			return;
		}
		else if (pos == 0)
		{
			ListPopFront();
			return;
		}
		else
		{
			ListNode* cur = _head;
			int n = pos+1;
			while (n--)
			{
				cur = cur->_next;
			}
			ListNode* next = cur->_next;
			ListNode* prev = cur->_prev;
			prev->_next = next;
			next->_prev = prev;
			delete cur;
		}
		Length--;
	}
	//销毁
	~List()
	{
		ListNode* cur = _head;
		ListNode* next = _head;
		while (next!=nullptr)
		{
			next = cur->_next;
			delete cur;
			cur = next;
		}
	}
private:
	ListNode* _head;
	int Length = 0;
};

int main()
{
	List<char> l1;
	l1.ListPushFront('a');
	l1.printList();

	l1.ListPushBack('c');
	l1.printList();

	l1.ListInsert(1, 'b');
	l1.printList();

	l1.ListErase(1);
	l1.printList();

	l1.ListPopBack();
	l1.printList();


	l1.ListPopFront();
	l1.printList();

	return 0;
}

